Fractions, division and Bresenham lines
Introduction
Many years while figuring out how to draw lines using 68000 I had the chance to quickly look at that great bible, Computer Graphics Principles and Practice. At the time I didn't really understand all those pages of maths concerning the Bresenham line algorithm, so came up with a far, far simpler explaination. As far as I know, everyone still uses Bresenham's descriptions to explain how it works. In this article, I'll explain it from a different point of view.
NOTE: This article focuses on the hidden divisions of the Bresenham algorithm.
Lines and division
Let's skip over the dodgy looking ASCII and normal line definitions and start with two end-points (x1,y1) and (x2,y2). We'll consider how to draw a line from (10,20) to (99,39) which gives us a horizontal length of 90 pixels and vertical length of 20 pixels. After dividing the horizontal length (major axis) by the vertical length (minor axis) we get 90/20 = 4.5
In short we need to draw the entire line by using a number of 4.5 horizontal pixel spans.
Fractions and Totals
But we can't draw 0.5 of a pixel, so we must either draw 4 or 5 pixels. To deal with the above problem of 4.5 pixels we seperate the integer part, use that to know how big the span should be and then add the fractional part to a total. Once that total becomes greater or equal to 1.0 we draw an extra pixel.
Think of it this way:
Instead of trying to draw 4.5 pixels then a second 4.5 pixels (ie. 9 pixels), we could draw 4 pixels then 4+1 pixels and still reach our 9.
The very clever part in the Bresenham algorithm is the way it performs 2 divisions using just ADD and SUBTRACT. As we'll see in a short while there is one (very obvious) division for the Integer part and one (slightly hidden) division to obtain the fraction part.
Division through subtraction
As you all know multiplication can be performed using repeated additions (4n = n + n + n + n). Also division can be done through repeated subtraction.
num = 90
divisor = 20
count = 0
remainder = num
again:
count = count + 1
remainder = num - divisor
if remainder >= divisor then goto again
Running the above code should give you count=4 and remainder=10 which is exactly right.
mov bx, 90 ; num = 90
mov cx, 20 ; divisor = 20
init:
mov ax, 0 ; count = 0
mov dx, bx ; remainder = num
again:
inc ax ; count + 1
sub dx, cx ; remainder - divisor
cmp dx, cx ; is remainder >= divisor ?
jae again
Integer division and spans
Okay, there has been nothing ground breaking so far. The previous code performs an integer division just like the DIV and IDIV instructions and gives us the remainder too (remainder = num MOD divisor).
It seems like we can modify it to perform a line drawing algorithm. We plot a pixel inside the above 'span' loop and then re-initialise the remainder and count variables and then loop back to draw the required number of spans (in our example case, 20 of ~4 pixel spans).
example:
mov bp, 20 ; number of spans
span:
mov bx, 90 ; num = 90
mov cx, 20 ; divisor = 20
init:
mov ax, 0 ; count = 0
mov dx, bx ; remainder = num
again:
mov ES:[di], 5 ; plot pixel, color 5
inc di ; x + 1
inc ax ; count + 1
sub dx, cx ; remainder - divisor
cmp dx, cx ; is remainder >= divisor ?
jae again
add di, 320 ; y + 1
dec bp
jnz span ; another span ?
BUT, we have forgotten about the fraction part.
Performing the above example code will only give us 20 spans of 4 pixels (80 pixels), but we wanted to draw 20 spans of 4.5 pixels (90 pixels!!).
Using remainders to store fractions
You may think we need to use some more variables (or registers) to store the fraction to handle that 0.5 part, but we can simply use the remainder to do this.
90 / 20 = 4.5 integer part 4
fractional part 0.5
int (90/20) = 4 integer part
90 mod 20 = 10 remainder
Look closely at that remainder value and the divisor (20).
10 / 20 = 0.5 fractional part !
remainder / divisor = fractional part
which is:-
(num MOD divisor) / divisor = fractional part
If we modify the repeated-subtraction for division so that instead of initialising 'remainder = num' we add to the remainder and do this 'remainder = remainder + num' then that 10 remainder will soon cause an extra iteration of that 'again' loop which will draw that extra pixel.
This means we draw 5 pixels instead of 4. We have totaled up all those 0.5 fractions until we get >= 1.0
Don't worry if you don't understand it, here is some lame QBASIC code.
CLS
num = 90
divisor = 20
remainder = num
spancount = 20
span:
count = 0
again:
count = count + 1
remainder = remainder - divisor
IF remainder >= divisor THEN GOTO again
PRINT count
remainder = remainder + num
spancount = spancount - 1
IF spancount > 0 THEN GOTO span
Please note how the count value toggles between 4 and 5, this is because we are performing an integer division (using repeated subtraction) AND we are also totaling up all those remainder values of the integer division. Eventually that remainder value (10 in our example) we become large enough to cause an extra iteration of the division loop (10 + 10 = 20, which is >= divisor value).
Closing Words
I hope you understood all that. Sorry if you didn't, just try some different values for yourself (like 10 and 3) and look at the result in count after each span. I still find it amazing that we are able to perform an integer and a fractional divide simply be replacing MOV with an ADD instruction.
Bressy rules.